import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main_1 {

	private static final long MOD = 1000000009L;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCases = Integer.parseInt(br.readLine());
		while (testCases-- != 0) {
			int n = Integer.parseInt(br.readLine());
			List<Long> a = convertToLong(br.readLine(), n);
			
			long maxSum = getMaxSubSum(a.toArray(new Long[0]));
			System.out.println(maxSum + " " + findSubSetSumCount(a, maxSum));
		}
	}
	
	//public static void main(String[] args) throws Exception {
		//long[] a = new long[] {-3, -2, 0, 2};
		
		//List<Long> longArray = Arrays.asList(1L, -1L, 1L, -1L, 1L);
		//List<Long> longArray = Arrays.asList(-200L, -100L, -100L, -400L, -232L, -10000009L);
//		List<Long> longArray = Arrays.asList(2L, 4L, 6L);
//		System.out.println(findSubSetSumCount(longArray, 6L));
	//}
	
	
	private static long findSubSetSumCount( List<Long> longArray, long maxSum) {
		Collections.sort(longArray);
		
		Long[] a = longArray.toArray(new Long[0]);
		long positiveMax = findPositiveSum(a);
		long negativeMax = findNegativeSum(a);
		
		long[] numArray = new long[(int)(-negativeMax + positiveMax + 1)];
		populateNumArray(numArray, positiveMax, negativeMax);
		
		long[][] memTable = new long[(int)a.length + 1][(int)numArray.length];
		for(int i = 0; i <= a.length; i++) {
			memTable[i][(int)-negativeMax] = 1; 
		}
		
		for(int i = 1; i <= a.length; i++) {
			for(int j = 0; j < numArray.length; j++) {
					memTable[i][j] = (((-negativeMax + (numArray[j] - a[i - 1]) >= 0 && (-negativeMax + (numArray[j] - a[i - 1])) < numArray.length) ? memTable[i -1][(int)(-negativeMax + (numArray[j] - a[i - 1]))] : 0) + memTable[i - 1][j]) % MOD;
			}
		}
		return memTable[a.length][(int)(-negativeMax + maxSum)];
	}
	
	private static void populateNumArray(long[] numArray, Long positiveMax, Long negativeMax) {
		int i = 0;
		while(negativeMax != 0) {
			numArray[i++] = negativeMax++;
		}
		
		i = numArray.length - 1;
		while(positiveMax != 0) {
			numArray[i--] = positiveMax--;
		}
	}
	
	private static long findPositiveSum(Long[] a) {
		long sum = 0;
		for(int i = 0; i < a.length; i++) {
			if(a[i] >= 0) {
				sum += a[i];
			}
		}
		return sum;
	}
	
	private static long findNegativeSum(Long[] a) {
		long sum = 0;
		for(int i = 0; i < a.length; i++) {
			if(a[i] < 0) {
				sum += a[i];
			}
		}
		return sum;
	}

	
	private static long getMaxSubSum(Long[] a) {
		long maxSum = 0;
		boolean maxSumFound = false;
		long maxElement = Long.MIN_VALUE;
		for(int i = 0; i < a.length; i++) {
			if(a[i] >= 0) {
				maxSumFound = true;
				maxSum += a[i];
			}
			maxElement = Math.max(maxElement, a[i]);
		}
		
		if(maxSumFound) {
			return maxSum;
		} else {
			return maxElement;
		}
	}
	
	private static List<Long> convertToLong(String str, int n) {
		StringTokenizer sToken = new StringTokenizer(str, " ");
		List<Long> list = new ArrayList<Long>();
		for(int i = 0; i < n; i++) {
			list.add(Long.parseLong(sToken.nextToken()));
		}
		return list;
	}
}